package violentRecursion;

import java.util.List;

/*
 *@description 三角形最小路径和
 *@author hkfan
 *@version 1.0
 *@create 2025/6/23 16:50
 */
public class LeetCode_120 {

    public int minimumTotal(List<List<Integer>> triangle) {
        return solution_2(triangle,0,0);
    }

    /**
    * @Description: 暴力递归
    * @Author: kunkun
    * @Date:  2025/7/1 15:21
    */
    private int solution_1(List<List<Integer>> triangle, int index, int i) {
        if (index==triangle.size()){
            return 0;
        }
        int res1 = solution_1(triangle,index+1,i)+triangle.get(index).get(i);
        int res2 = (i+1<triangle.get(index).size())?solution_1(triangle,index+1,i+1)+triangle.get(index).get(i+1):Integer.MAX_VALUE;
        return Math.min(res1,res2);
    }

    /**
    * @Description: 动态规划
    * @Author: kunkun
    * @Date:  2025/7/1 15:21
    */
    private int solution_2(List<List<Integer>> triangle, int index, int x) {
        int[][] dp = new int[triangle.size()+1][triangle.get(triangle.size()-1).size()];
        for (int i = triangle.size()-1; i >=0; i--) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                int res1 = dp[i+1][j]+triangle.get(i).get(j);
                int res2 = (j+1<triangle.get(i).size())?dp[i+1][j+1]+triangle.get(i).get(j+1):Integer.MAX_VALUE;
                dp[i][j] = Math.min(res1,res2);
            }
        }
        return dp[0][0];
    }

}